package org.zdw.data.structure.sort;

/**
 * 算法思想：基于分治的思想，是冒泡排序的改进型。
 * 首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法），
 * 然后分别从数组的两端扫描数组，设两个指示标志（lo指向起始位置，hi指向末尾)，首先从后半部分开始，
 * 如果发现有元素比该基准点的值小，就交换lo和hi位置的值，然后从前半部分开始扫秒，发现有元素大于基准点的值，
 * 就交换lo和hi位置的值，如此往复循环，直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了。
 * 以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。
 */
public class QuickSort {

    public void sort(int[] array){
        if (array.length > 0) { //查看数组是否为空
            _quickSort(array,0, array.length - 1);
        }
    }

    private int getMiddle(int[] list,int low,int high){
        int tmp =list[low]; //数组的第一个作为中轴
        while (low < high){
            while (low < high&& list[high] >= tmp) {
                high--;
            }

            list[low] =list[high]; //比中轴小的记录移到低端
            while (low < high&& list[low] <= tmp) {
                low++;
            }

            list[high] =list[low]; //比中轴大的记录移到高端
        }
        list[low] = tmp;  //中轴记录到尾
        return low;   //返回中轴的位置
    }

    public void _quickSort(int[] list, int low, int high) {
        if (low < high){
            int middle =getMiddle(list, low, high); //将list数组进行一分为二
            _quickSort(list, low, middle - 1); //对低字表进行递归排序
            _quickSort(list,middle + 1, high); //对高字表进行递归排序
        }
    }
}
